Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes

Identifieur interne : 000040 ( Main/Exploration ); précédent : 000039; suivant : 000041

Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes

Auteurs : Frédéric Bihan [France] ; Pierre-Jean Spaenlehauer [France]

Source :

RBID : Hal:hal-01217547

Abstract

Consider a regular triangulation of the convex-hull $P$ of a set $\mathcal A$ of $n$ points in $\mathbb R^d$, and a real matrix $C$ of size $d \times n$. A version of Viro's method allows to construct from these data an unmixed polynomial system with support $\mathcal A$ and coefficient matrix $C$ whose number of positive solutions is bounded from below by the number of $d$-simplices which are positively decorated by $C$. We show that all the $d$-simplices of a triangulation can be positively decorated if and only if the triangulation is balanced, which in turn is equivalent to the fact that its dual graph is bipartite. This allows us to identify, among classical families, monomial supports which admit maximally positive systems, i.e. systems all toric complex solutions of which are real and positive. These families give some evidence in favor of a conjecture due to Bihan. We also use this technique in order to construct fewnomial systems with many positive solutions. This is done by considering a simplicial complex with bipartite dual graph included in a regular triangulation of the cyclic polytope.

Url:


Affiliations:


Links toward previous steps (curation, corpus...)


Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes</title>
<author>
<name sortKey="Bihan, Frederic" sort="Bihan, Frederic" uniqKey="Bihan F" first="Frédéric" last="Bihan">Frédéric Bihan</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-79" status="VALID">
<orgName>Laboratoire de Mathématiques</orgName>
<orgName type="acronym">LAMA</orgName>
<desc>
<address>
<addrLine>Université de Savoie, UFR SFA Domaine Universitaire, Bâtiment Le Chablais 73376 LE BOURGET DU LAC</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lama.univ-savoie.fr/</ref>
</desc>
<listRelation>
<relation name="UMR5127" active="#struct-441569" type="direct"></relation>
<relation active="#struct-432896" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle name="UMR5127" active="#struct-441569" type="direct">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-432896" type="direct">
<org type="institution" xml:id="struct-432896" status="VALID">
<orgName>Université Savoie Mont Blanc</orgName>
<orgName type="acronym">USMB [Université de Savoie] [Université de Chambéry]</orgName>
<date type="start">1979-10-01</date>
<desc>
<address>
<addrLine>27, rue Marcoz - 73000 Chambéry</addrLine>
<country key="FR"></country>
</address>
<ref type="url">https://www.univ-smb.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Spaenlehauer, Pierre Jean" sort="Spaenlehauer, Pierre Jean" uniqKey="Spaenlehauer P" first="Pierre-Jean" last="Spaenlehauer">Pierre-Jean Spaenlehauer</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID">
<idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation>
<relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-129671" type="direct">
<org type="laboratory" xml:id="struct-129671" status="VALID">
<idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc>
<address>
<addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct">
<org type="department" xml:id="struct-423083" status="VALID">
<orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation>
<relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect">
<org type="laboratory" xml:id="struct-206040" status="VALID">
<idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc>
<address>
<addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect">
<org type="institution" xml:id="struct-413289" status="VALID">
<idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc>
<address>
<addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01217547</idno>
<idno type="halId">hal-01217547</idno>
<idno type="halUri">https://hal.inria.fr/hal-01217547</idno>
<idno type="url">https://hal.inria.fr/hal-01217547</idno>
<date when="2016-04-18">2016-04-18</date>
<idno type="wicri:Area/Hal/Corpus">004666</idno>
<idno type="wicri:Area/Hal/Curation">004666</idno>
<idno type="wicri:Area/Hal/Checkpoint">000040</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000040</idno>
<idno type="wicri:Area/Main/Merge">000040</idno>
<idno type="wicri:Area/Main/Curation">000040</idno>
<idno type="wicri:Area/Main/Exploration">000040</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en">Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes</title>
<author>
<name sortKey="Bihan, Frederic" sort="Bihan, Frederic" uniqKey="Bihan F" first="Frédéric" last="Bihan">Frédéric Bihan</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-79" status="VALID">
<orgName>Laboratoire de Mathématiques</orgName>
<orgName type="acronym">LAMA</orgName>
<desc>
<address>
<addrLine>Université de Savoie, UFR SFA Domaine Universitaire, Bâtiment Le Chablais 73376 LE BOURGET DU LAC</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lama.univ-savoie.fr/</ref>
</desc>
<listRelation>
<relation name="UMR5127" active="#struct-441569" type="direct"></relation>
<relation active="#struct-432896" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle name="UMR5127" active="#struct-441569" type="direct">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-432896" type="direct">
<org type="institution" xml:id="struct-432896" status="VALID">
<orgName>Université Savoie Mont Blanc</orgName>
<orgName type="acronym">USMB [Université de Savoie] [Université de Chambéry]</orgName>
<date type="start">1979-10-01</date>
<desc>
<address>
<addrLine>27, rue Marcoz - 73000 Chambéry</addrLine>
<country key="FR"></country>
</address>
<ref type="url">https://www.univ-smb.fr</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Spaenlehauer, Pierre Jean" sort="Spaenlehauer, Pierre Jean" uniqKey="Spaenlehauer P" first="Pierre-Jean" last="Spaenlehauer">Pierre-Jean Spaenlehauer</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID">
<idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation>
<relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-129671" type="direct">
<org type="laboratory" xml:id="struct-129671" status="VALID">
<idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc>
<address>
<addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct">
<org type="department" xml:id="struct-423083" status="VALID">
<orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation>
<relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect">
<org type="laboratory" xml:id="struct-206040" status="VALID">
<idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc>
<address>
<addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect">
<org type="institution" xml:id="struct-413289" status="VALID">
<idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc>
<address>
<addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc>
<textClass></textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">Consider a regular triangulation of the convex-hull $P$ of a set $\mathcal A$ of $n$ points in $\mathbb R^d$, and a real matrix $C$ of size $d \times n$. A version of Viro's method allows to construct from these data an unmixed polynomial system with support $\mathcal A$ and coefficient matrix $C$ whose number of positive solutions is bounded from below by the number of $d$-simplices which are positively decorated by $C$. We show that all the $d$-simplices of a triangulation can be positively decorated if and only if the triangulation is balanced, which in turn is equivalent to the fact that its dual graph is bipartite. This allows us to identify, among classical families, monomial supports which admit maximally positive systems, i.e. systems all toric complex solutions of which are real and positive. These families give some evidence in favor of a conjecture due to Bihan. We also use this technique in order to construct fewnomial systems with many positive solutions. This is done by considering a simplicial complex with bipartite dual graph included in a regular triangulation of the cyclic polytope.</div>
</front>
</TEI>
<affiliations>
<list>
<country>
<li>France</li>
</country>
<region>
<li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement>
<li>Metz</li>
<li>Nancy</li>
</settlement>
<orgName>
<li>Université de Lorraine</li>
</orgName>
</list>
<tree>
<country name="France">
<noRegion>
<name sortKey="Bihan, Frederic" sort="Bihan, Frederic" uniqKey="Bihan F" first="Frédéric" last="Bihan">Frédéric Bihan</name>
</noRegion>
<name sortKey="Spaenlehauer, Pierre Jean" sort="Spaenlehauer, Pierre Jean" uniqKey="Spaenlehauer P" first="Pierre-Jean" last="Spaenlehauer">Pierre-Jean Spaenlehauer</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000040 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000040 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-01217547
   |texte=   Sparse Polynomial Systems with many Positive Solutions from Bipartite Simplicial Complexes
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022